package LRU;

import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;

/**
 * 获取数组子集元素和最大值
 * Created by luoqifei on 2017/8/23.
 */
public class SonArr {
    public static int getMaxSubSum(int start,int[] src){
        int sum = src[start];
        int maxSum = sum;
        for(int i=start+1;i<src.length;i++){
            sum+=src[i];
            if(sum> maxSum){
                maxSum = sum;
            }
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] arr = {2,5,-1,3,-9,8,5,-5,4};
        LinkedList<Integer> meta = new LinkedList<Integer>();
        HashMap<String,String> index = new HashMap<String, String>();
        for(int i=0;i<arr.length;i++){
            meta.add(SonArr.getMaxSubSum(i,arr));
        }
        Collections.sort(meta);
        System.out.println(meta.get(meta.size()-1));
    }
}
